# 83/100 动态规划-完全平方数(好题)
# leetcode第198题: https://leetcode.cn/problems/perfect-squares/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/19
import math
from functools import cache

from leetcode import test


def numSquares(n: int) -> int:
    """使用动态规划的方法"""
    dp = [float('inf')] * (n + 1)  # dp[i] 表示和为整数i需要的最少完全平方数的个数
    dp[0] = 0
    dp[1] = 1
    for i in range(2, n + 1):
        for j in range(1, int(math.sqrt(i)) + 1):
            dp[i] = min(dp[i - j * j] + 1, dp[i])
    return int(dp[n])


def numSquares_opt(n: int) -> int:
    """优化的DP方法"""
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    dp[1] = 1

    # 建立完全平方数数组perfect squares
    ps = [i * i for i in range(1, int(math.sqrt(n) + 1))]

    for i in range(len(ps)):
        for j in range(ps[i], n + 1):
            dp[j] = min(dp[j - ps[i]] + 1, dp[j])
    return int(dp[n])


def numSquares_dfs(n: int) -> int:
    """ @cache 缓存函数的计算结果，当函数被调用时，如果传入的参数与之前调用时相同，那么将直接返回之前计算好的结果，
    而不再重新执行函数体中的代码，从而显著提高函数的执行效率，特别是对于那些计算成本较高且参数相同的函数调用。
    此外还有 @lru_cache 和 @cached_property 这两个装饰器
    https://blog.csdn.net/captain5339/article/details/131434063
    """

    @cache  # 缓存装饰器，避免重复计算 dfs 的结果
    def dfs(i: int, j: int) -> int:
        if i == 0:
            return float('inf') if j else 0
        if j < i * i:
            return dfs(i - 1, j)  # 只能不选
        return min(dfs(i - 1, j), dfs(i, j - i * i) + 1)  # 不选 vs 选

    return dfs(math.isqrt(n), n)


def numSquares_math(n: int) -> int:
    """使用数学定理[四平方和定理](https://baike.baidu.com/item/%E5%9B%9B%E5%B9%B3%E6%96%B9%E5%92%8C%E5%AE%9A%E7%90%86)
    四平方和定理说明每个正整数均可表示为4个整数的平方和。因此提供了一个推论 $n \neq 4^k \times (8m + 7)$ 时，n表示为至多3个正整数的平方和，
    因此当$n = 4^k \times (8m + 7)$ 时， n就只能表示为四个正整数的平方和
    """

    # 判断一个数字是否是完全平方数
    if int(math.sqrt(n)) ** 2 == n:
        return 1

    # 检查 n == 4^k(8m + 7)， 如果是则只能是4
    while (n // 4) * 4 == n:  # reduce 4^k
        n /= 4
    if n % 8 == 7:
        return 4

    # 检查数字是否是两个完全平方数的和 也就是 n = a * a + b * b
    for i in range(1, int(math.sqrt(n)) + 1):
        rem = n - i * i
        if int(math.sqrt(rem)) ** 2 == rem:
            return 2

    return 3


if __name__ == '__main__':
    inp = [{"n": 12}, {"n": 13}, {"n": 100}, ]
    out = [3, 2, 1]

    test.test_function(numSquares, inp, out, times=100)
    test.test_function(numSquares_opt, inp, out, times=100)
    test.test_function(numSquares_dfs, inp, out, times=100)
    test.test_function(numSquares_math, inp, out, times=100)
